package exercise;


import test.list.PriorityQueue;

import java.util.*;

public class Exercise005 {
    //HashSet/HashMap
    public static void test3(){
        int[] nums = {1,2,3,1,2,3};
        int k = 2;
        for(int i = 0;i < nums.length - k;i++){
            for(int j = i + 1;j <= i + k;j++){
                if(nums[i] == nums[j]){
                    System.out.println(true);
                    return;
                }
            }
        }
        System.out.println(false);
    }

    public static void test2(){
        int[] nums = {9,2,3,3,2};
        Map<Integer,Integer> map = new HashMap();
        for(int n:nums){
            int count = map.getOrDefault(n,0);
            map.put(n,count + 1);
        }
        for(Map.Entry<Integer,Integer> entry:map.entrySet()){
            if(entry.getValue() == 1){
                System.out.println(entry.getKey());
            }
        }
    }

    //七大排序算法
    public static void test1(){
        int[] arr = {7,30,2,1,6,8,5,80,20,10};

//        System.out.println("插入排序");
//        System.out.println(Arrays.toString(arr));
//        insertSort(arr);

//        System.out.println("希尔排序");
//        System.out.println(Arrays.toString(arr));
//        shellSort(arr);

//        System.out.println("选择排序");
//        System.out.println(Arrays.toString(arr));
//        selectSort(arr);

//        System.out.println("堆排序");
//        System.out.println(Arrays.toString(arr));
//        heapSort(arr);

//        System.out.println("冒泡排序");
//        System.out.println(Arrays.toString(arr));
//        bubbleSort(arr);

//        System.out.println("快速排序--递归");
//        System.out.println(Arrays.toString(arr));
//        quickSort1(arr);

//        System.out.println("快速排序--非递归");
//        System.out.println(Arrays.toString(arr));
//        quickSort2(arr);

        System.out.println("归并排序---递归");
        System.out.println(Arrays.toString(arr));
        mergeSort1(arr);

//        System.out.println("归并排序---非递归");
//        System.out.println(Arrays.toString(arr));
//        mergeSort2(arr);

//        System.out.println("计数排序");
//        System.out.println(Arrays.toString(arr));
//        countSort(arr);

        System.out.println(Arrays.toString(arr));
    }
    public static void main(String[] args){
//        test1();
//        test2();
        test3();
    }

    //七大排序算法
    // 插入排序
    //将第一个待排序元素插入已排序区间合适位置
    //循环直至length - 1
    //时间复杂度：O（n ^ 2）
    //空间复杂度：O（1）
    //稳定性：稳定
    public static void insertSort(int[] array){
        for(int bound = 1;bound < array.length;bound++) {
            int val = array[bound];
            int cur = bound - 1;
            for(;cur >= 0;cur--){
                if(array[cur] > val){
                    array[cur + 1] = array[cur];
                }else{
                    break;
                }
            }
            array[cur + 1] = val;
            System.out.print("第" + bound + "趟：");
            System.out.println(Arrays.toString(array));
        }
    }


    // 希尔排序
    //先按每gap步为一组分为gap组
    //每组进行插入排序
    //gap--直到gap为1
    //时间复杂度：不确定
    //空间复杂度：O（1）
    //稳定性：不稳定
    public static void shellSort(int[] array){
        int gap = array.length / 2;
        while(gap > 0){
            shellSortHelper(array,gap);
            System.out.print("gap = " + gap + "：");
            System.out.println(Arrays.toString(array));
            gap /= 2;
        }
    }
    public static void shellSortHelper(int[] array,int gap){
        for(int bound = gap;bound < array.length;bound++) {
            int val = array[bound];
            int cur = bound - gap;
            for(;cur >= gap - 1;cur -= gap){
                if(array[cur] > val){
                    array[cur + gap] = array[cur];
                }else{
                    break;
                }
            }
            array[cur + gap] = val;
        }
    }


    // 选择排序
    //从未排序区间中选出最小排到bound - 1的位置
    //直到 bound == array.length 结束循环
    //时间复杂度：O（n ^ 2）
    //空间复杂度：O（1）
    //稳定性：稳定
    public static void selectSort(int[] array){
        for(int bound = 0;bound < array.length - 1;bound++) {
            int cur = bound + 1;
            for(;cur < array.length;cur++){
                if(array[cur] < array[bound]){
                    int tmp = array[bound];
                    array[bound] = array[cur];
                    array[cur] = tmp;
                }
            }
            int i = bound + 1;
            System.out.print("第" + i + "趟：");
            System.out.println(Arrays.toString(array));
        }
    }


    // 堆排序
    //建大堆，队首元素则为最大值
    //将队首元素与 bound - 1 位置的元素交换
    //向上调整使任符合大堆规则
    //循环直到bound == 1
    //时间复杂度：O（NlogN）
    //空间复杂度：O（1）
    //稳定性：不稳定
    public static void heapSort(int[] array){
        createHeap(array);
        System.out.print("建堆");
        System.out.println(Arrays.toString(array));
        int bound = array.length - 1;
        for(int i = 1;i < array.length;i++){
            int tmp = array[bound];
            array[bound] = array[0];
            array[0] = tmp;
            bound--;
            shiftDown(0,array,bound);
            System.out.print("第" + i + "趟：");
            System.out.println(Arrays.toString(array));
        }
    }
    public static void createHeap(int[] array) {
        for(int i = (array.length - 1 - 1) / 2;i >= 0;i--){
            shiftDown(i,array,array.length);
        }
    }
    private static void shiftDown(int index,int[] array,int len) {
        if(len == 1){
            return;
        }
        int parent = index;
        int child = index * 2 + 1;
        while(child < len){
            if(child + 1 < len && array[child] < array[child + 1]){
                child++;
            }
            if(array[parent] < array[child]){
                int tmp = array[parent];
                array[parent] = array[child];
                array[child] = tmp;
            }else{
                break;
            }
            parent = child;
            child = parent * 2 + 1;
        }
    }


    // 冒泡排序
    //进行 数组长度 趟交换
    //每趟交换都能把最大值排到最后
    //直到某趟交换 未进行前后交换
    //时间复杂度：O（N ^ 2）
    //空间复杂度：O（1）
    //稳定性：稳定
    public static void bubbleSort(int[] array){
        for(int i = 0;i < array.length - 1;i++){
            boolean flag = false;
            for(int j = 0; j < array.length - i - 1;j++){
                if(array[j] > array[j + 1]) {
                    int tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                    flag = true;
                }
            }
            int n = i + 1;
            System.out.print("第" + n + "趟：");
            System.out.println(Arrays.toString(array));
            if(flag == false){
                break;
            }
        }
    }

    // 快速排序--递归
    //取数组最后一个元素作为标准值
    //先让 i 从左往右遍历，找到比基准值大的值
    //再让 j 从右往左遍历，找到比基准值小的值
    //如果 j 遍历时和 i 相等了，结束循环，交换 基准值 和 array[i] 的值
    //如果 i != j ，交换 array[i] 和 array[j] 的值
    //j == i 后，一趟交换结束，i 作为中间值不动，递归交换 i 两边的元素
    //如果 交换区间left >= right，此时不触发交换，直接返回
    //时间复杂度：O（NlogN）
    //空间复杂度：O（logN）
    //稳定性：不稳定
    static int num = 1;
    public static void quickSort1(int[] array){
        num = 1;
        quickSort1(array,0, array.length - 1);
    }

    public static void quickSort1(int[] array,int left,int right){
        if(right - left <= 1){
            return;
        }

        //交换分离成两部分
        int index = partition(array,left,right);

        //进行下一轮交换
        quickSort1(array,left,index - 1);
        quickSort1(array,index + 1,right);

    }

    private static int partition(int[] array, int left, int right) {
        int tail = array[right];
        int i = left;
        int j = right;

        while(true){
            //从左往右找比 tail 大的值
            for(;i < right;i++){
                if(array[i] > tail){
                    break;
                }
            }

            //从右往左找比 tail 小的值
            for(;j > left;j--){
                if(j == i){
                    break;
                }
                if(array[j] < tail){
                    break;
                }
            }


            if(j == i){
                //如果 i == j，此时第一轮交换结束
                //把数组最后的基准值与 i 下标的元素交换
                swap(array,i,right);
                System.out.print("第" + num + "趟：");
                num++;
                System.out.println(Arrays.toString(array));
                break;
            }else{
                //交换两者位置
                swap(array,i,j);
            }
        }

        return i;
    }

    private static void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    // 快速排序--非递归
    public static void quickSort2(int[] array){
        num = 1;
        quickSort2(array,0, array.length - 1);
    }

    private static void quickSort2(int[] array, int left, int right) {
        Stack<Integer> stack = new Stack<>();
        stack.push(right);
        stack.push(left);

        while(!stack.isEmpty()){
            left = stack.pop();
            right = stack.pop();

            if(right - left <= 1){
                continue;
            }

            int mid = partion1(array,left,right);

            //先入右边
            stack.push(right);
            stack.push(mid + 1);

            //再入左边
            stack.push(mid - 1);
            stack.push(left);
        }
    }

    private static int partion1(int[] array, int left, int right) {
        int tail = array[right];
        int i = left;
        int j = right;

        while(true){
            //从左往右找比 tail 大的值
            for(;i < right;i++){
                if(array[i] > tail){
                    break;
                }
            }

            //从右往左找比 tail 小的值
            for(;j > left;j--){
                if(j == i){
                    break;
                }
                if(array[j] < tail){
                    break;
                }
            }

            if(j == i){
                //如果 i == j，此时第一轮交换结束
                //把数组最后的基准值与 i 下标的元素交换
                swap(array,i,right);
                System.out.print("第" + num + "趟：");
                num++;
                System.out.println(Arrays.toString(array));
                break;
            }else{
                //交换两者位置
                swap(array,i,j);
            }
        }
        return i;
    }

    // 归并排序---递归
    //把数组分为相对平均的左右两部分
    //分组若干次后每组都为有序区间（单独的一个元素自成有序区间）
    //将这若干组两两合并
    //合并后的若干数组两两合并
    //直到合并为一个大数组
    //时间复杂度：O（NlogN）
    //空间复杂度：O（N）
    //稳定性：稳定
    public static void mergeSort1(int[] array){
        num = 1;
        mergeSort1(array,0,array.length - 1);
    }

    private static void mergeSort1(int[] array,int left,int right) {
        if(right <= left){
            return;
        }

        int mid = (right + left) / 2;

        //分别递归 左右无序区间
        mergeSort1(array,left,mid);
        mergeSort1(array,mid + 1,right);

        //合并
        merge(array,mid,left,right);
        System.out.print("第" + num + "趟：");
        num++;
        System.out.println(Arrays.toString(array));
    }

    private static void merge(int[] array, int mid, int left, int right) {
        int[] result = new int[right - left + 1];
        int resultSize = 0;
        int i = left;
        int j = mid + 1;
        while(i <= mid && j <= right){
            //如果 array[i] 小则拼接，否则拼接 array[j]
            //拼接后循环变量迭代
            //如果迭代后超出限定长度，循环结束
            if(array[i] <= array[j]){
                result[resultSize++] = array[i];
                i++;
            }else{
                result[resultSize++] = array[j];
                j++;
            }
        }
        //如果前半区间仍有元素未拼接
        while(i <= mid){
            result[resultSize++] = array[i];
            i++;
        }
        //如果后半区间仍有元素未拼接
        while(j <= right){
            result[resultSize++] = array[j];
            j++;
        }
        i = left;
        for(resultSize = 0;resultSize < result.length;resultSize++){
            array[i] = result[resultSize];
            i++;
        }
    }


    // 归并排序---非递归
    public static void mergeSort2(int[] array){
        num = 1;
        for(int size = 1;size < array.length;size *= 2){
            for(int i = 0;i < array.length;i += size * 2){
                int left = i;
                int mid = i + size - 1;
                if(mid >= array.length){
                    mid = array.length - 1;
                }
                int right = i + 2 * size - 1;
                if(right >= array.length){
                    right = array.length - 1;
                }
                merge(array,mid,left,right);
                System.out.print("第" + num + "趟：");
                num++;
                System.out.println(Arrays.toString(array));
            }
        }
    }


    // 计数排序
    //遍历数组找到 最大值max 和 最小值min
    //创建count数组，数组长度为 max - min + 1
    //遍历数组，数组元素 - min 即为 count数组 下标，访问并自增
    //稳定性：稳定
    public static void countSort(int[] array){
        int max = array[0];
        int min = array[0];
        for(int i = 1;i < array.length;i++){
            if(array[i] > max){
                max = array[i];
            }
            if(array[i] < min){
                min = array[i];
            }
        }
        int[] count = new int[max - min + 1];
        for(int i = 0;i < array.length;i++){
            int index = array[i] - min;
            count[index]++;
        }
        System.out.print("[");
        for(int i = 0;i < count.length;i++){
            while(count[i] != 0){
                System.out.print(i + min);
                count[i]--;
                if(i != count.length - 1) {
                    System.out.print(",");
                }
            }
        }
        System.out.print("]");
    }

}
